package depthorder;

import entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class ComOrderTraversal {
    /*
    * 前中后序统一迭代
    *
    * 使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
    * 那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
    * 如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
    * */
    public static void main(String[] args){

    }

    // 先
    public List<Integer> preOder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            root = stack.peek();
            if(root != null){   // 不等于null，不需要现在处理
                stack.pop();   // 弹出，避免重复处理
                if(root.right != null) stack.push(root.right);  // 添加右节点
                if(root.left != null) stack.push(root.left);    // 添加左节点
                stack.push(root);   // 把中节点加回去
                stack.push(null);   // 中节点访问过，但是还没有处理，加入空节点做为标记。
            }
            else {  // 只有遇到null才进行处理
                stack.pop();    // 弹出空节点
                res.add(stack.pop().val);   // 该节点入结果
            }
        }
        return res;
    }

    // 中
    public List<Integer> inOder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            root = stack.peek();
            if(root != null){   // 不等于null，不需要现在处理
                stack.pop();   // 弹出，避免重复处理
                if(root.right != null) stack.push(root.right);  // 先添加右节点
                stack.push(root);   // 把中节点加回去
                stack.push(null);   // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if(root.left != null) stack.push(root.left);    // 添加左节点
            }
            else {  // 只有遇到null才进行处理
                stack.pop();    // 弹出空节点
                res.add(stack.pop().val);   // 该节点入结果
            }
        }
        return res;
    }

    // 后
    public List<Integer> postOder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            root = stack.peek();
            if(root != null){   // 不等于null，不需要现在处理
                stack.pop();   // 弹出，避免重复处理
                stack.push(root);   // 把中节点加回去
                stack.push(null);   // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if(root.right != null) stack.push(root.right);  // 添加右节点
                if(root.left != null) stack.push(root.left);    // 添加左节点
            }
            else {  // 只有遇到null才进行处理
                stack.pop();    // 弹出空节点
                res.add(stack.pop().val);   // 该节点入结果
            }
        }
        return res;
    }
}
